package com.LeeCode;

/**
 * 长度为 n 的开心字符串中字典序第 k 小的字符串
 */

public class Code1415 {
    public static void main(String[] args) {
        int n = 1, k = 3;
        System.out.println(new Code1415().getHappyString(n, k));
    }

    private int k;

    public String getHappyString(int n, int k) {
        int total = 3 * (1 << (n - 1));
        if (k > total) return "";
        this.k = k;
        StringBuilder cur = new StringBuilder();
        backtrace(0, cur, n);
        return cur.toString();
    }

    private boolean backtrace(int index, StringBuilder cur, int n) {
        if (index == n) {
            if (--k == 0) return true;
            return false;
        }

        for (int i = 0; i < 3; i++) {
            if (index == 0) {
                cur.append((char) ('a' + i));
                if (backtrace(index + 1, cur, n)) return true;
                cur.setLength(0);
            } else {
                int prev = cur.charAt(index - 1) - 'a';
                if (i == prev) continue;
                cur.append((char) ('a' + i));
                if (backtrace(index + 1, cur, n)) return true;
                cur.deleteCharAt(cur.length() - 1);
            }
        }
        return false;
    }
}
